package leetcode;

public class RangeSumQuery {

	public static void main(String[] args) {
		int[] nums = {1, 5, 6, 3, 9, -8};
		RangeSumQuery object = new RangeSumQuery(nums);
		System.out.println(object.sumRange(2, 5));
		object.update(2, -1);
		System.out.println(object.sumRange(2, 5));
		object.update(1, 3);
		System.out.println(object.sumRange(1, 3));
	}
	
	
	int[] nums;
    int[] segmentTree;
    public RangeSumQuery(int[] nums) {
        this.nums = nums;
        if(nums == null || nums.length <= 0){
            return;
        }
        //内存占用大约为4倍的点数，所以建数组的时候为4 * N
        segmentTree = new int[nums.length * 4];
        build(0, 0, nums.length - 1);
        System.out.println("----");
        for (int i = 0; i < segmentTree.length; i++) {
			System.out.print(segmentTree[i] + "  ");
		}
        System.out.println();
    }
    
    public void build(int num, int left, int right) {
    	System.out.println("num: " + num);
    	if(left == right){  
    		segmentTree[num] = nums[left];
	        return;  
	    }  
		int mid = (left + right) / 2;
		System.out.println("num: " + num + " middle: " + mid);
		build(num * 2 + 1, left, mid);
		build(num * 2 + 2, mid + 1, right);
		//这个根据具体情况具体写，题目上是求和，所以这里是加
		//如果变成最大值，那么这儿应该相应的改成最大值
		segmentTree[num] = segmentTree[num * 2 + 1] + segmentTree[num * 2 + 2];
	}

    public void update(int i, int val) {
    	update(0, 0, nums.length - 1, i, val - nums[i]);
    	nums[i] = val;
    }
    
    public void update(int num, int left, int right, int x, int y) {
		if (left == right) {
			segmentTree[num] += y;
			return;
		}
		int mid = (left + right) / 2;
		//寻找到x所对应的tree[num]
		if (x <= mid){
			update(num * 2 + 1, left, mid, x, y);
		}else{
			update(num * 2 + 2, mid + 1, right, x, y);
		}
		segmentTree[num] = segmentTree[num * 2 + 1] + segmentTree[num * 2 + 2];
	}

    public int sumRange(int i, int j) {
        return query(0, 0, nums.length - 1, i, j);
    }
    
    public int query(int num, int left, int right, int x, int y) {
		//此时tree[num]就已经是这一部分的有效数据了，所以直接return即可
		if (x <= left && y >= right) {
			return segmentTree[num];
		}
		int mid = (left + right) / 2;
		int ans = 0;
		if (x <= mid)
			ans += query(num * 2 + 1, left, mid, x, y);
		if (y > mid)
			ans += query(num * 2 + 2, mid + 1, right, x, y);
		return ans;
	}
}
